package com.mgq.algorithm.dp;

/**
 * 一个合法的括号匹配序列有以下定义:
 * ①空串""是一个合法的括号匹配序列
 * ②如果"X"和"Y"都是合法的括号匹配序列,"XY"也是--个合法的括号匹配序列
 * ③如果"X"是一个合法的括号匹配序列,那么" (X) "也是一个合法的括号匹配序列
 * ④每个合法的括号序列都可以由以上规则生成。
 * 例如: "","()","() ()","(()))”都是合法的括号序列
 * 对于一个合法的括号序列我们又有以下定义它的深度:
 * ①空串""的深度是0
 * ②如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为
 * max(x,y) 3、如果"X"的深度是x,那么字符串" (X)"的深度是x+1
 * 给的是合法的括号.所以直接操作就行,count最大值就是
 * 例如: "()() ()"的深度是1,"((()))"的深度是3。牛牛现在给你一-个合法的括号
 * 序列,需要你计算出其深度。
 */
public class Bracket {

    /**
     * 这道题不要想的太复杂.题目说给的是合法的括号,那么只需要从左,遍历,找到最大的count值就是答案
     * @param str
     * @return
     */
    public static int deep(String str) {
        if ("".equals(str)) return 0;
        char[] chars = str.toCharArray();
        int count=0;
        int max=0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '(') {
                count++;
            } else {
                max=Math.max(max,count);
                count--;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(deep("((()))"));
        System.out.println(deep("(((())))()"));
        System.out.println(deep("()(())"));
    }
}
